There is an ever increasing need for efficiency in creating, modifying and searching data structures. This need is particularly pertinent to routing problems, in which the goal is to find the correct destination(s) for every incoming request, as quickly and efficiently as possible. Typical routing problems include the routing of network addresses used by the Internet Protocol; the routing of logical units used by the IBM Standards Communication Architecture (SNA) protocol; and other general routing mechanisms, to name a few examples.
Although efficiency is important for routing problems, the need for efficiency in creating, modifying and searching data structures is not unique to routing problems. Efficiency is just as important in other situations in which information needs to be gathered for a given request. For example, in Telenet applications, when a user logs on to a computer, information about the user is needed. This information includes, for instance, the applications to be started during log on and the printer to be used by the user. This information needs to be collected as fast as possible in order to provide an efficient log on.
One searchable data structure that has been used, particularly in routing problems, is a PATRICIA (Practical Algorithm to Retrieve Information Coded in Alphanumeric) tree. The PATRICIA tree organization is based on a binary tree that enables searching for exact key matches.
However, if the requested key is part of a group and the exact match is not found, then the PATRICIA tree organization fails to provide a way to find a best match for the key. That is, it does not provide a solution to find the next smaller or next bigger element than the requested key. Additionally, the PATRICIA tree organization does not lead to an efficient technique for traversing the tree in either ascending or descending order. Specifically, the PATRICIA tree organization does not provide for the ordering of keys.
Based on the foregoing, a data structure and search technique are needed that allow for efficiency in locating a best match for a given key. A further need exists for an efficient technique for traversing a data structure in ascending or descending order. Another need exists for a general search data structure and techniques that can be used in many applications, including, but not limited to, routing and Telenet applications.